1. Field of the Invention
This invention relates to transmission of digital information. More particularly, this invention relates to cache operations in the routing of packets in data switching networks.
2. Description of the Related Art
The meanings of certain acronyms and abbreviations used herein are given in Table 1.
TABLE 1Acronyms and AbbreviationsDIPDestination Internet Protocol AddressDRAMDynamic Random Access MemoryHCAHost Channel AdapterIPInternet ProtocolLPMLongest Prefix MatchMSBMost Signficant BitsNICNetwork Interface CardRIFRouter InterfaceSRAMStatic Random Access MemoryTCAMTernary Content Addressable Memory
Modern internet routers determine data routing based on searching for a packet destination IP address (DIP) in a database of forwarding information known as a routing table. The routing table, rather than storing a full DIP, stores only some of the leading portion, known as a prefix. The prefix comprises some number of the most significant bits of the DIP. The remaining bits are treated as “don't care” bits for purpose of a DIP search in the routing table. However they specify a subnetwork or subnet. Computers that belong to a subnetwork are addressed by a common prefix in their IP address.
The most specific of the matching table entries—the one with the longest subnet mask—is called the longest prefix match (LPM). This is the entry in the routing table in which the largest number of leading address bits of the destination address match those in the table entry.
Searching the routing table for the LPM is a bottleneck in routing throughput. Various hardware-based solutions have been proposed. However, the circuitry required to implement such solutions becomes complex. Moreover, the increasing amount of internet traffic and demands for reduced latency have resulted in relatively costly router circuitry having high power consumption and heat dissipation.
For example, the document, A Cache-Based Internet Protocol Address Lookup Architecture, Soraya Kasnavi et al., Computer Networks 52 (2008) 303-326, proposes a Ternary Content Addressable Memory (TCAM) with a hardware-based LPM matching method. However, TCAM memory, while reducing the number of hash lookups, is expensive.
One option to ease the performance of an IP lookup is to implement a cache. In contrast to an LPM algorithm running on the main database, the cache can provide a lookup result with a single access to the cache database. Only searches that result in a cache miss require an IP address search by the LPM algorithm. Caching assumes that within a short period of time the same IP address is searched multiple times.
It is well known that traffic in networks in general and on the Internet in particular is not uniformly distributed. Rather, the traffic has been shown to follow a heavy tail distribution that can be modeled with a power law of a Zipf distribution. Such distributions are observed per prefix, per IP address and per flow showing that in all cases most of the traffic concentrates on a small percentage of all the elements. This distribution can be exploited in a well-constructed caching scheme.
A number of solutions have been proposed for LPM caching. Some of them employ the same algorithm on the cache and on an external device or network element, e.g., a DRAM, a router or other network device. Other schemes make caching independent of the algorithm used in the external device. In one configuration an SRAM acts as a cache for the external device.
The simplest solution for caching is to find an exact match so that each IP address is cached as an entry on the SRAM. This may be sufficient in many cases. However, the number of IP addresses covered by the cache can be dramatically increased using the LPM feature. In general, any prefix that has no compatible longer prefix can be directly cached and used on a match. However, for prefixes that have longer compatible prefixes, caching can cause a “cache hiding” problem unless all the longer compatible prefixes have also been cached. A packet to one such longer compatible prefix that is not in the cache will be incorrectly routed according to a shorter prefix stored in the cache.
There are different ways to deal with cache hiding. In one solution when a prefix is placed in the cache all longer compatible prefixes are also placed. However, this is complex to implement, particularly eviction from the cache. In a simpler approach, the length of the longest prefix that is present in the routing table is used for caching. This was explored in the document Revisiting Route Caching: the World Should Be Flat”, C. Kim et al., Proceedings of the 10th International Conference on Passive and Active Network Measurement (PAM), but under the assumption that prefixes longer that /24 were not present in the table or were handled using a small additional table. The solution creates a /24 entry on the cache for a packet and effectively caches 256 subnet addresses per entry (2(32-24)=28=256). However, a direct implementation of the scheme is impractical because there may be prefixes up to /32 in the table.
Another approach involves expansion of the routing table to ensure that it has no compatible prefixes, as proposed in the document Efficient Fib Caching Using Minimal Non-Overlapping Prefixes, Y. Liu, S. O. Amin and L. Wang, ACM SIGCOMM Computer Communication Review, January 2013. For example, if there is a /24 prefix with a compatible /32 prefix, /25, /26, . . . , /31 prefixes that are not compatible in the last bit with the /32 prefix are created. Those prefixes include patterns of all possible DIP addresses in the /24 prefix other than the /32 prefix. Therefore, for the purpose of routing they are equivalent to the /24 prefix when the /32 prefix is present.